import java.util.*;
import java.util.Stack;
import java.util.Arrays;

class IndexWrong extends RuntimeException{
    public IndexWrong() {
    }

    public IndexWrong(String message) {
        super(message);
    }
}

class EmptyException extends RuntimeException {
    public EmptyException() {
        //这是一个提示顺序表为空的异常
    }

    public EmptyException(String massage) {
        super(massage);
    }
}

class PosWrongfulException extends RuntimeException{
    public PosWrongfulException() {
        //PosWrongfulException 一个提示不合法的异常
    }

    public PosWrongfulException(String massage) {
        super(massage);
    }
}

// 排序算法实现
class TestSort {

    /**
     * 直接插入排序
     */
    public static void insertSort(int[] array1) {
        //i下标从数组的第二个值开始
        for (int i = 1; i < array1.length; i++) {
            int tmp = array1[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= 0; j--) {
                if (array1[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array1[j + 1] = array1[j];
                } else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array1[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序（直接排序的优化）
     */
    public static void shellSort(int[] array2) {
        int gap = array2.length;//为数组的长度 - 为10
        while (gap > 1) {
            gap /= 2;//先是分成了5组，然后是2组，再是1组
            shell(array2, gap);//调用直接插入排序方法
        }
    }

    //实现直接插入排序方法
    public static void shell(int[] array2, int gap) {
        //i下标从第一组的第二个数据开始
        for (int i = gap; i < array2.length; i++) {
            int tmp = array2[i];//tmp存放i下标的值
            int j = i - gap;//j下标为i-gap个位置
            //j每次-gap个位置
            for (; j >= 0; j -= gap) {
                if (array2[j] > tmp) {
                    //j下标的值大，将j下标的值放到j变量加上一个gap的位置上
                    array2[j + gap] = array2[j];
                } else {
                    //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
            array2[j + gap] = tmp;
        }
    }

    /**
     * 选择排序1
     */
    public static void selectSort(int[] array3) {
        for (int i = 0; i < array3.length; i++) {
            int minIndex = i;//假设最小值是当前的i下标的值
            for (int j = i + 1; j < array3.length; j++) {
                if (array3[j] < array3[minIndex]) {
                    //更新
                    minIndex = j;//将此时的j下标的值赋给minIndex
                }
            }
            if (i != minIndex) {
                //调用交换的方法交换i下标的值和minIndex的值
                swap(array3, minIndex, i);
            }
        }
    }

    //交换的方法
    public static void swap(int[] array3, int i, int j) {
        int tmp = array3[i];
        array3[i] = array3[j];
        array3[j] = tmp;
    }

    /**
     * 选择排序2
     */
    public static void selecstSort(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;//假设最小值在左边
            int maxIndex = left;//假设最大值在左边
            //i下标位于第二个位置
            for (int j = left + 1; j <= right; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
                if (array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            //把最小值交换到前面
            swap(array, minIndex, left);
            //把最大值交换到前面
            swap(array, maxIndex, right);
            left++;
            right--;
        }
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] array) {
        creatBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }
    }

    //建堆
    public static void creatBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            //调用向下调整
            shiftDown(array, parent, array.length);
        }
    }

    //向下调整的方法
    public static void shiftDown(int[] array, int parent, int len) {
        int child = (2 * parent) + 1;
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        //最外层控制的是趟数
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = true;
                }
            }
            if (flag = false) {
                break;
            }
        }
    }

    /**
     * 快速排序 Hoare版
     */
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quick(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个数据
        int pivot = array[left];//将第一个数据给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }

            swap(array, left, right);//调用方法交换左边和右边的值
        }
        //此时已经遍历完成
        swap(array, left, i);//调用非法交换第一个元素和此时left的值
        return left;//返回的就是找到的基准
    }

    /**
     * 快速排序优化 挖坑法版
     * 优化了查找基准的方法
     */
    public static void quickSorts(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quicks(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partitions(int[] array, int left, int right) {
        int pivot = array[left];//将坑位的数据   给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }
            array[right] = array[left];
        }
        //和原来的 left交换
        array[left] = pivot;
        return left;//返回的就是找到的基准
    }

    /**
     * 快速排序优化 前后指针版
     * 优化了查找基准的方法
     */
    public static void quickSortsx(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quicksx(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partitionsx(int[] array, int left, int right) {
        int prev = left;//在第一个数据
        int cur = left + 1;//在第二个数据
        while (left <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);//调用方法交换左边和右边的值
            }
            cur++;//指向下一个
        }
        swap(array, prev, left);
        return prev;//返回基准
    }

    /**
     * 快速排序 数组有序的情况
     */
    public static void quickSort1(int[] array) {
        quick1(array, 0, array.length - 1);
    }

    //非递归实现快排
    public static void isNotRecursiveQuickSort(int[] array) {
        //定义栈
        Stack<Integer> stack = new Stack<>();
        //定义开始和结束的位置变量
        int start = 0;//是下标0
        int end = array.length - 1;//是数组长度减1
        int pivot = partition(array, start, end);//调用找基准的方法
        //判断左边是不是只有一个数据
        if (pivot > (start + 1)) {
            //不止一个数据 - 将start和end的下标压入到栈中
            stack.push(start);//压入0下标
            stack.push(pivot - 1);//压入此时的4下标
        }
        //判断右边是不是只有一个数据
        if (pivot < (end - 1)) {
            //此时不止一个数据 - 将start和end下标压入栈中
            stack.push(pivot + 1);//压入此时的6下标
            stack.push(end);//压入此时的9下标
        }
        //栈不为空才可以弹出
        while (!stack.isEmpty()) {
            end = stack.pop();//先弹栈顶给end
            start = stack.pop(); //再弹栈顶给start
            //再次找新的基准和新的区间
            pivot = partition(array, start, end);//调用找基准的方法
            //判断左边是不是只有一个数据
            if (pivot > (start + 1)) {
                //不止一个数据 - 将start和end的下标压入到栈中
                stack.push(start);//压入start下标
                stack.push(pivot - 1);//压入此时的end下标
            }
            //判断右边是不是只有一个数据
            if (pivot < (end - 1)) {
                //此时不止一个数据 - 将start和end下标压入栈中
                stack.push(pivot + 1);//压入此时的start下标
                stack.push(end);//压入此时的end下标
            }
        }
    }

    private static void insertSort(int[] array1, int left, int right) {
        //i下标从数组的左边第二个值开始
        for (int i = left + 1; i <= right; i++) {
            int tmp = array1[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= left; j--) {
                if (array1[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array1[j + 1] = array1[j];
                } else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                    break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array1[j + 1] = tmp;
        }
    }

    public static void quick1(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //快排优化
        if (end - start + 1 >= 15) {
            //对start和end范围内的使用插入排序
            insertSort(array, start, end);
            return;
        }
        //在执行 partition1 前，尽量解决划分不均匀的问题
        int index = findMidValOfIndex(array, start, end);//接受三个数中间大小的值
        swap(array, start, index);
        //接收基准
        int pivot = partition1(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //找中间大小的值 - 三数取中法
    public static int findMidValOfIndex(int[] array, int start, int end) {
        //如果数据是有序的情况要将它均分
        int minIndex = (start + end) / 2;
        if (array[start] < array[end]) {
            if (array[minIndex] < array[start]) {
                return start;//返回的是中间值
            } else if (array[minIndex] > array[end]) {
                return end;
            } else {
                return minIndex;
            }
        } else {
            if (array[minIndex] > array[start]) {
                return start;
            } else if (array[minIndex] < array[end]) {
                return end;
            } else {
                return minIndex;
            }
        }
    }

    //查找基准的方法
    public static int partition1(int[] array, int left, int right) {
        int i = left;//存储第一个数据
        int pivot = array[left];//将第一个数据给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }

            swap(array, left, right);//调用方法交换左边和右边的值
        }
        //此时已经遍历完成
        swap(array, left, i);//调用非法交换第一个元素和此时left的值
        return left;//返回的就是找到的基准
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        mergeSortChild(array, 0, array.length - 1);
    }

    //分解的方法
    public static void mergeSortChild(int[] array, int left, int right) {
        //分解
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;//中间位置
        mergeSortChild(array, left, mid);//递归1分解左边
        mergeSortChild(array, mid + 1, right);//递归右边
        //开始合并
        mergre(array, left, mid, right);
    }

    //合并的方法
    public static void mergre(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;//记录数组下标
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                //数组下标加1个 指向下一个
                tmpArr[k++] = array[s1++];
            } else {
                //这是s2小的情况 -将s2的值放到数组中
                tmpArr[k++] = array[s2++];
            }
        }
        //此时是s1或者s2超出区间范围了，但是有可能有一个还未超出范围
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //此时数组中的数据是有序的了 - 此时要将排序好的数组传到原来的数组中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArr[i];
        }
    }

    /**
     * 归并排序非递归实现
     */
    public static void isNotNotRecursiveMergeSort(int[] array) {
        int gap = 1;//先假定每一个数都是单独有序的
        while (gap < array.length) {
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i;//左边是i下标的位置
                int mid = left + gap - 1;//中间的位置
                int right = gap + mid;
                //防止right和mid越界
                if (mid >= array.length) {
                    mid = array.length - 1;//放到新位置
                }
                if (right >= array.length) {
                    right = array.length - 1;//放到新位置
                }
                //开始归并 - 调用之前的合并方法
                mergre(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    /**
     * 计数排序
     */
    public static void countSort(int[] array) {
        //遍历数组找到最大值和最小值 - 找到才能确定数组的长度
        int maxVal = array[0];//假设最大值在0下标
        int minVal = array[0];//假设最小值在0下标
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                //此时i下标的值为最大值
                maxVal = array[i];
            }
            if (array[i] < minVal) {
                //此时i下标为最小值
                minVal = array[i];
            }
        }
        //确定数组的长度
        int len = maxVal - minVal + 1;
        int[] countArr = new int[len];
        //遍历数组统计每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            countArr[val - minVal]++;
        }
        int index = 0;
        //此时计数完毕 - 看每个下标的值是几就打印几
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i + minVal;
                index++;
                countArr[i]--;
            }
        }
    }
}

// 二叉树实现
class TestBinaryTree {
    //孩子表示法实现二叉树
    static class TreeNode {
        //1.建立数据域、左孩子的引用和右孩子的引用
        public char val;
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //开始创建二叉树
    public TreeNode createTree() {
        //2.创建二叉树的结点
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');

        //3.有左孩子赋值到左边，有右孩子的赋值到右边并确定根节点
        treeNodeA.left = treeNodeB;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeA.right = treeNodeC;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;//确定根节点
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        System.out.print(root.val + " ");//打印此时根节点
        preOrder(root.left);//访问左边
        preOrder(root.right);//访问右边
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        inOrder(root.left);//访问左边
        System.out.print(root.val + " ");//打印此时根节点
        inOrder(root.right);//访问右边
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        postOrder(root.left);//访问左边
        postOrder(root.right);//访问右边
        System.out.print(root.val + " ");//打印此时根节点
    }

    //求二叉树的结点个数
    //1.遍历的思路
    public static int nodeSize = 0;//计数器

    public int size(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        nodeSize++;
        size(root.left);//访问左边
        size(root.right);//访问右边
        return nodeSize;//返回计数器的值
    }

    //2.递归求解
    public int nodeSize(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        return nodeSize(root.left) + nodeSize(root.right) + 1;//左树加右树加1
    }

    //1.遍历获取二叉树的叶子结点个数
    public static int leafSize = 0;//叶子计数器

    public int getLeafNodeCount(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空 - 两个都为空即是叶子
        if (root.left == null && root.right == null) {
            leafSize++;//叶子个数加1
        }
        //调用方法访问左孩子和右孩子
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;//返回叶子个数
    }

    //2.递归获取叶子结点个数
    public int leafNodeSize(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        if (root.left == null && root.right == null) {
            return 1;//叶子结点数
        }
        //左边的叶子和右边的叶子相加
        return leafNodeSize(root.left) + leafNodeSize(root.right);
    }

    //递归实现获取第k层的节点个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        //不能为空，层数不能是0或者负数
        if (root == null || k <= 0) {
            return 0;
        }
        //k是第一层的情况
        if (k == 1) {
            return 1;//直接返回1
        }
        //大于1的情况 - 左树的k-1层加上右数的k-1层
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    //递归实现获取二叉树的高度
    public int getHeight(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        int leftHeight = getHeight(root.left);//求左树的高度
        int rightHeight = getHeight(root.right);//求右树的高度
        //返回左右树的最大值加1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //递归查找val值是否存在
    public TreeNode findVal(TreeNode root, char val) {
        //为空
        if (root == null) {
            return null;
        }
        //不为空的情况
        //根节点此时的值等于我要查找的值
        if (root.val == val) {
            //返回此时root的地址
            return root;
        }
        //root此时的值不等于我要查找的值 - 调用方法访问左右两边的值
        TreeNode leftVal = findVal(root.left, val);//访问左边
        //此时左边的值不为空就继续找
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = findVal(root.right, val);//访问右边
        //此时右边的值不为空就继续找
        if (rightVal != null) {
            return rightVal;
        }
        //整个树都访问完了就说明没有val值
        return null;
    }

    //非递归实现层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //不为空 - 实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        //压入元素到队列中
        queue.offer(root);
        //队列不为空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();//弹出给cur
            //同时打印队头的元素
            System.out.print(cur.val + " ");
            //如果cur的左边不是空的说明未遍历结束
            if (cur.left != null) {
                //继续压入元素到队列中
                queue.offer(cur.left);
            }
            //如果cur右边不是空的说明未遍历结束
            if (cur.right != null) {
                //继续压入
                queue.offer(cur.right);
            }
        }
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //为空的情况
        if (root == null) {
            return true;//是完全二叉树
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//将此时root结点放到队列中
        //队列不为空
        while (!queue.isEmpty()) {
            //弹出此时队列的队头元素
            TreeNode cur = queue.poll();
            //压入root的左和右
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        //判断队列剩下的值是否有非null的数据
        while (!queue.isEmpty()) {
            TreeNode popValue = queue.poll();//弹出此时队头的元素
            //如果队列中有非null的元素则不是完全二叉树
            if (popValue != null) {
                return false;
            }
        }
        //若循环结束说明都为空 - 即是完全二叉树
        return true;
    }
}

// 循环队列实现
class MyCircularQueue {

    private int[] elem;
    public int front;//队头
    public int rear;//队尾

    public MyCircularQueue(int k) {
        elem = new int[k + 1];
    }

    //入队列
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }

    public boolean isFull() {
        if((rear+1) % elem.length == front) {
            return true;
        }
        return false;
    }


    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front = (front+1) % elem.length;
        return true;
    }

    public boolean isEmpty() {
        if(front == rear) {
            return true;
        }
        return false;
    }
    //获取队头元素
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = rear == 0 ? elem.length-1 : rear-1;
        return elem[index];
    }
}

// 顺序表实现
class MyArrayList {
    private int[] elem; //未初始化的数组
    private int usedSize; //记录有效的数据个数
    public static final int DEFAULT_SIZE = 10;

    //构造方法
    public MyArrayList() {
        this.elem = new int[DEFAULT_SIZE];//数组大小为10个元素
    }

    //打印顺序表中所有的元素，这并不是顺序表中的方法，而是为了观看测试结果给出的
    public void disPlay() {
        for (int i = 0; i < this.usedSize; i++) {//usedSize是有效数据个数
            System.out.print(this.elem[i] + " "); //元素之间加上空格
        }
        System.out.println();//输出完后换行
    }

    //检查顺序表是否满了的方法
    public boolean isFull() {
        //size()是获取顺序表长度的方法

        /*if (size() >= this.elem.length) { //满了
            return true;
        }else { //没满
            return false;
        }*/

        //优化过后的写法 - 会自动比较出一个true || false
        return size() >= this.elem.length;
    }

    //默认在顺序表最后新增元素 - data是要新增的元素
    public void add(int data) {
        //1. 检查当前的顺序表是不是满了
        //isFull()方法中会有一个值来表示当前顺序表是不是满了
        if (isFull()) {
            //2. 如果满了 就要进行扩容
            //将elem扩容位原来的2倍
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        //3.新增元素
        //当前usedSize(有效元素个数)的值就是顺序表末尾的下标 - 要想新增赋值即可
        this.elem[this.usedSize] = data;

        //4.有效元素个数加1 - usedSize
        this.usedSize++;
    }

    /**
     * 如果 pos 下标不合法就会抛出一个异常
     */
    //在顺序表指定位置新增 - 在pos位置新增元素- data是要新增的元素
    //throws PosWrongfulException可以提示调用者这个地方可能会有一个异常
    public void add(int pos, int data) throws PosWrongfulException{
        //1.负数下标不可以
        //2.要存储的位置pos前面一定是有元素的
        //usedSize在这里指的是顺序表末尾的位置下标
        if (pos < 0 || pos > this.usedSize) { //pos是指定新增位置的下标
            System.out.println("位置不合法！！！");

            //抛一个异常
            throw new PosWrongfulException("位置不合法！！！");
        }
        if (isFull()) {
            //3.超过数组长度不可以
            //满了就扩容
            System.out.println("顺序表满了");
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        //程序执行到这里就可以插入一个元素了
        //1.开始挪动数据
        //从顺序表末位位置开始向后移动，直到遇到 pos 位置
        for (int i = this.usedSize - 1; i >= pos; i--) { //usedSize-1指的是顺序表末位位置的下标
            this.elem[i + 1] =  this.elem[i];
        }

        //2.在顺序表中插入一个元素
        this.elem[pos] = data; //data是要插入个元素

        //3.顺序表元素加1 - usedSize
        this.usedSize++; //顺序表有效元素个数加一个
    }

    //判定是否包含某个元素 - toFind是我要判定的元素
    public boolean contains(int toFind) {
        //size()方法求的是顺序表的长度
        for (int i = 0; i < this.size(); i++) {
            if (this.elem[i] == toFind) {
                return true; //找到了
            }
        }
        return false;///没找到
    }

    //查找某个对应元素的位置 - toFind是我要查找的元素
    public int indexOf (int toFind) {
        //size()方法求的是顺序表的长度
        for (int i = 0; i < this.size(); i++) {
            //若顺序表存储的是引用数据类型，该怎么比较？要使用 equals()来比较
            if (this.elem[i] == toFind) {
                return i; //找到了 - 返回下标
            }
        }
        return -1;//没找到 - 返回-1
    }

    public boolean isEmpty() {
        //size()方法求的是顺序表有效元素个数
        return size() == 0;//根据比较的值来返回true或者false
    }

    //获取 pos 元素的位置
    public int get(int pos) {
        if (isEmpty()) {
            //顺序表有可能是空的 - 抛异常来提示
            throw new EmptyException("当前顺序表为空！！！");
        }
        if (pos < 0 || pos >= usedSize) {
            //查找位置的下标可能是负数 - 也可能超过了顺序表的长度 - 抛异常来提示
            throw new PosWrongfulException("get获取元素的时候，pos位置不合法！！！");
        }
        return this.elem[pos]; //此时pos下标就是要找的位置
    }

    //给 pos 位置的元素更新为 value
    public void set(int pos, int value) {
        //1.顺序表不是空的
        if (isEmpty()) {
            //顺序表有可能是空的 - 抛异常来提示
            //这里要注意的是此方法是用来更新的，即使是空间满了也不需要扩容
            throw new EmptyException("当前顺序表为空！！！");
        }

        //2.pos位置要合法 - 下标不为负数，不超过数组长度
        if (pos < 0 || pos >= usedSize) {
            //查找位置的下标可能是负数 - 也可能超过了顺序表的长度 - 抛异常来提示
            throw new PosWrongfulException("set获取元素的时候，pos位置不合法！！！");
        }

        //开始更新
        this.elem[pos] = value; //value是更新后的值
    }

    //删除第一次出现的关键字 Key - Key是多次出现的元素
    public void remove (int Key) {
        //1.空的顺序表没有 Key
        if (isEmpty()) {
            //因为作用是删除，即使是空表也不需要扩容
            throw new EmptyException("顺序表为空！！！");
        }
        int index = indexOf(Key);//查找Key位置的下标
        if (index == -1) {
            System.out.println("没有这个数字！！！");
            return;
        }

        //2.要先找到key，才能知道下标
        //数组是从要删除的元素开始遍历，直到遇到在数组末尾的有效数据元素结束
        for (int i = index; i < usedSize - 1; i++) {
            //3.挪动数据
            this.elem[i] = this.elem[i + 1];//将顺序表后一个元素向前一个元素的位置覆盖
        }

        //4，顺序表长度减1
        this.usedSize--;//顺序表长度减1
    }

    //获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    //清空顺序表
    public void clear() {
        //如果顺序表存储的是引用类型的数据则要将表置为null
        /*for (int i = 0; i < usedSize; i++) { //0表示的是表的第一个元素，遍历完整个表结束
            this.elem[i] = null;//将每一个元素董志伟空
        }*/

        //如果是普通类型，则置为0
        this.usedSize = 0;
    }
}

class MyemptyStackException extends RuntimeException{
    public MyemptyStackException() {
    }

    public MyemptyStackException(String message) {
        super(message);
    }
}

// 栈实现
class MyStack {
    public int[] elem; //数组
    public int usedSize; //栈的元素个数
    public static final int DEFAULT_SIZE = 10;

    public MyStack(int[] elem) {
        this.elem = new int[DEFAULT_SIZE];
    }

    //判断栈是不是空间满了的方法（隶属压栈方法）
    public boolean isFull() {
        return this.usedSize == elem.length;
    }

    //压栈
    public int push(int val) {
        //空间不够就扩容
        if (isFull()) {
            //为真就是满了 - 需要扩容
            elem = Arrays.copyOf(elem, 2 * elem.length); //将原来的数组长度扩大为原来的2倍
        }

        //从栈顶压入
        this.elem[this.usedSize] = val; //usedSize 下标就是栈顶的位置
        this.usedSize++;//元素个数加1
        return val;
    }

    //判断栈是否为空的方法（隶属出栈方法）
    public boolean isEmpty() {
        return this.usedSize == 0;//为真就是空
    }

    //出栈
    public int pop() throws MyemptyStackException{
        //栈是空的就无法出栈
        if (isEmpty()){
            //为空
           throw new MyemptyStackException("栈为空！！！");
        }
        return this.elem[--this.usedSize];//返回此时的栈顶元素后元素个数减1
    }

    //peek操作 - 看一眼栈顶元素是什么，但是不拿出
    public int peek() throws MyemptyStackException{
        //栈是空的无法观察
        if (isEmpty()){
            //为空
            throw new MyemptyStackException("栈为空！！！");
        }
        return this.elem[this.usedSize - 1]; //返回的是数组的最后一个下标位置
    }
}


public class DataStructureExercise {
    //实现链表
    static class ListNode {
        public int value; //数值
        public ListNode next; //地址

        public ListNode (int value) {
           this.value = value;
        }
    }

    //创建一个指针
    public ListNode head; //头指针

    //创建链表的方法
    public void createList() {
        //创建5个结点
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        //使这5个结点连接起来
        listNode1.next = listNode2; //将第2个结点的地址给第1个结点
        listNode2.next = listNode3; //将第3个结点的地址给第2个结点
        listNode3.next = listNode4; //将第4个结点的地址给第3个结点
        listNode4.next = listNode5; //将第5个结点的地址给第4个结点

        //将头结点指向第1个结点，head结点里存了第1个结点的地址
        this.head = listNode1;
    }

    //打印链表
    public void disPlay() {
        //代替 head 移动
        ListNode cur = this.head;
        //遍历所有结点
        while (cur != null) {
            System.out.println("value:" + cur.value);
            cur = cur.next; //找到下一个
        }
        System.out.println();
    }

    //查找key是否在单链表中 - 存在返回true，不存在返回false
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.value == key) {
                return true;
            }
            cur = cur.next; //指向下一个
        }
        return false; //循环结束说明不存在
    }

    //头插法 - 插入结点到头部
    //头插法可以不考虑表是不是null - 即使表是空的node的地址域也是null，也能找到下一个结点
    public void addStart(int data) {
        //新建一个结点
        ListNode node = new ListNode(data);
        //先绑定后面再绑定前面
        node.next = this.head; //node结点的地址域保存当前头结点的地址
        this.head = node; //node结点变成了新的头结点
    }

    //尾插法 - 插入几点到尾部
    public void addEnd(int data) {
        //创建一个结点
        ListNode node = new ListNode(data);
        ListNode cur = this.head; //代替head移动

        //分两种情况 - 链表为空和不为空
        if (cur == null) {
            //链表为空 - 直接指向
            this.head = node;
        } else {
            // 不为空 - 要插入到尾部就先找到尾部
            while (cur.next != null) {
                cur = cur.next; //知道找到的结点为空为止
            }
            // 此时已找到链表的尾部,即是 cur 指向的位置
            cur.next = node; //保存node结点的地址使其串联起来
        }
    }

    //查找index位置的方法 （隶属在链表指定位置插入一个结点）
    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next; //找下一个
            index--; //缩小与 index 的位置
        }
        return cur; //此时 cur 指向的就是 index 的位置
    }

    //查找key前一个结点的方法 （隶属在链表指定位置插入一个结点）
    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        // 因为是找前一个结点。判断cur结点的下一个结点的地址即可
        while (cur.next!= null) {
            if (cur.next.value == key) {
                //找打了
                return cur;
            }
            //调整
            cur = cur.next;
        }
        //此时就肯定是找不到了
        return null;
    }

    //在链表指定位置插入一个结点
    public void addIndex(int index, int data) {  //index是位置，逻辑上定义的下标；data是要插入的结点
        // 创建结点
        ListNode node = new ListNode(data);

        //下标的位置不可能是负数也不能会超过链表的长度
        if (index < 0 || index > size()) {
            // 提示位置不合法
            System.out.println("index 的位置不合法!!!");
        }

        // 指定位置如果在头部就头插，在尾部就尾插
        //index 为 0 就是头插
        if (index == 0) {
            addStart(data);
            return;
        }
        //index为链表的长度就是 尾插
        if (index == size()) {
            addEnd(data);
            return;
        }

        // 剩下情况就是在中间插入
        //调用方法找到要插入的位置
        ListNode curIndex = findIndexSubOne(index); //curIndex 得到的是要插入的位置
        //改结点指向删除
        node.next = curIndex.next;
        curIndex.next = node;
    }

    //删除第一次出现的key结点
    public void remove(int key) {
        // 链表也可能是空的
        if (this.head == null) {
           return;
        }
        // 结点可能在链表的头部
        if (this.head.value == key) {
            System.out.println("要删除的结点不存在！！！");
            return;
        }

        //此时链表即不是空的key也不再 head 处
        ListNode curDelete = findPrevOfKey(key); //找到的是 key 结点的前一个结点

        // 链表可能不存在 key
        if (curDelete == null) {
            return;
        }
        ListNode delete = curDelete.next; //指向 key 的位置
        // 改指向删除
        curDelete.next = delete.next;
    }

    //删除所有key的结点
    public void removeAllKey(int key) {
        //链表为空直接返回
        if (this.head == null) {
            return;
        }

        ListNode precursor = this.head; //前驱
        ListNode successor = this.head.next; //后继
        while (successor != null) {
            // 判断是不是 key
            if (successor.value == key) {
                // 改指向删除
                precursor.next = successor.next;
                successor = successor.next;
            } else {
                precursor = successor;
                successor = successor.next; //指向下一个
            }
        }

        // 如果头结点是 key
        if (this.head.value == key) {
            this.head = this.head.next;
        }
    }

    //清空链表
    public void clear() {
        this.head = null; //将的结点置为空
    }

    //得到单链表的长度 - 结点个数
    public int size() {
        int count = 0; //计数器
        ListNode cur = this.head;
        while (cur != null) {
            count++; //个数加1
            cur = cur.next; //指向下一个
        }
        return count;
    }

    /*
     * Day 9
     * 1.从尾到头打印链表
     * 2.移除重复节点1前后指针法
     * */
    // 1.从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode bigHead = this.head;

        //如果bigHead不是空的就压栈
        while (bigHead != null) {
            stack.push(bigHead);
            bigHead = bigHead.next;
        }

        //得到栈的大小
        int size = stack.size();
        //创建数组
        int[] array = new int[size];
        for (int i = 0; i < array.length; i++) {
            array[i] = stack.pop().value;
        }
        return array;
    }

    // 2.移除重复节点1前后指针法
    public ListNode removeDuplicateNodes(ListNode head) {
        // 如果链表是空的。直接返回头结点
        if (this.head == null) {
            return this.head;
        }

        // 定义两指针
        ListNode prev = this.head;
        while (prev != null) {
            ListNode cur = prev;
            while (cur.next != null) {
                if (cur.next.value == prev.value) {
                    // 此时找到相同的结点 - 删除
                    cur.next = cur.next.next;
                } else {
                    // 不想同
                    cur = cur.next;
                }
            }
            prev = prev.next;
        }
        return this.head;
    }

    // 法2：哈西表方法
    /*public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.value);
        ListNode pos = head;
        // 枚举前驱节点
        while (pos.next != null) {
            // 当前待删除节点
            ListNode cur = pos.next;
            if (occurred.add(cur.value)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }*/

    /*
    * Day 10
    * 1.从链表中删去总和值为零的连续节点
    * 2.两数相加
    * */
    // 1.从链表中删去总和值为零的连续节点
    public ListNode removeZeroSumSublists(ListNode head) {

        ListNode d = new ListNode(-1);
        d.next = head;
        Map<Integer,ListNode> sumMap = new HashMap<>();
        sumMap.put(0,d);
        ListNode c = d;
        int sum = 0;
        while (c != null){
            sum += c.value;;
            sumMap.put(sum,c);
            c = c.next;
        }
        c = d;
        sum = 0;
        while (c != null){
            sum += c.value;
            if (sumMap.containsKey(sum)){
                ListNode node = sumMap.get(sum);
                c.next = node.next;
            }
            c = c.next;
        }
        return d.next;

        //前缀和+链表模拟
        // 求前缀和sum head = [1,2,-3,3,1] sum=[0,1,3,0,3,4]
        // 每当前缀和遇到一样的就表明这里有和为0的子段，我们可以以前面的遇到相同的优先处理
        /*ListNode dummy = new ListNode(0, this.head);
        ListNode cur = this.head;
        int sum = 0;
        while (cur != null) {
            sum += cur.value;
            cur.value = sum;
            cur = cur.next;
        }
        // printLinkList(dummy);
        HashMap<Integer, ListNode> map; // 存储值与节点引用映射关系
        boolean hasSame = true;
        while (hasSame) {
            map = new HashMap<>();
            cur = dummy;
            hasSame = false;
            while (cur != null) {
                if (!map.containsKey(cur.value)) {
                    // 还没找到相同的，加入
                    map.put(cur.value, cur);
                } else {
                    // 找到相同的，剪断并退出
                    map.get(cur.value).next = cur.next;
                    hasSame = true;
                    break;
                }
                cur = cur.next;
            }
        }
        // 从前缀和还原
        cur = this.head;
        int pre1 = 0, pre2;
        while (cur != null) {
            pre2 = cur.value;
            cur.value -= pre1;
            pre1 = pre2;
            cur = cur.next;
        }
        return dummy.next;*/
    }

    //2.两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.value : 0;
            int n2 = l2 != null ? l2.value : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    /*
    * Day 11
    * 1.排序链表
    * 2.奇偶链表
    * */
    // 1.排序链表
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.value <= temp2.value) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }

    // 2.奇偶链表
    public ListNode oddEvenList(ListNode head) {
        if (this.head == null) {
            return this.head;
        }
        ListNode evenHead = this.head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return this.head;
    }

    /*
     * Day 12
     * 1.合并两个有序链表
     * 2.删除链表中重复的结点
     * */
    // 1.合并两个有序链表
    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            //说明head1小
            if (head1.value < head2.value) {
                tmp.next = head1;
                head1 = head1.next;
            }else { //说明和head2小
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;//返回的是合并后的头结点
    }

    // 2.删除链表中重复的结点
    public ListNode deleteDuplication(ListNode pHead) {
        //空链表
        if (pHead == null) {
            return null;
        }
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = pHead;
        ListNode cur = res;
        while (cur.next != null && cur.next.next != null) {
            //遇到相邻两个节点值相同
            if (cur.next.value == cur.next.next.value) {
                int temp = cur.next.value;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.value == temp)
                    cur.next = cur.next.next;
            } else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }

    /*
     * Day 13
     * 1.翻转链表
     * 2.环形链表 II
     * */
    // 1.翻转链表
    public ListNode reverseList(ListNode head) {
        //链表为空的情况
        if (this.head == null) {
            return null;
        }

        //一个结点的情况
        if (head.next == null){
            return this.head;
        }
        //1.先定义一个cur
        ListNode cur = this.head.next;

        //2.把head结点置为null
        this.head.next = null;//这个时候作为头结点的head就与后面的结点断开了

        //3.采用头插法依次将head后面的结点头插到head之前
        //先定义一个curNext始终指向cur.next
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;//cur的地址域指向head的地址 - 这就插到了head之前
            head = cur;//head指向了当前头结点的位置
            cur = curNext;//cur指向它的下一个结点
        }
        return this.head;
    }

    // 2. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            //两个结点不一样的速度在走
            fast = fast.next.next;
            slow = slow.next;
            //两个相遇说明有环
            if (fast == slow) {
                break;
            }
        }

        //2种情况：循环条件不满足，一种是遇到break
        if (fast == null || fast.next == null) {
            return null;//如果为空则没有环
        }

        //fast和slow此时指向相遇点
        slow = this.head;//让slow重新指向head
        while (slow != fast) {
            slow = slow.next;
            fast = fast .next;
        }
        return fast;
    }

    /*
     * Day 14
     * 1. 用栈操作构建数组
     * 2.下一个更大元素 I
     * */
    // 1.  用栈操作构建数组
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<String>();
        int prev = 0;
        for (int number : target) {
            for (int i = 0; i < number - prev - 1; i++) {
                res.add("Push");
                res.add("Pop");
            }
            res.add("Push");
            prev = number;
        }
        return res;
    }

    // 2.下一个更大元素 I
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }

    /*
     * Day 15
     * 1.最小栈
     * 2.有效的括号
     * */
    // 1.最小栈
    class MinStack {

        public MinStack() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public void push(int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    //2.有效的括号
    public boolean isValid(String str) {
        //定义一个栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < str.length(); i++) {
            char chLeft = str.charAt(i);
            //判断是不是左括号
            if (chLeft == '(' || chLeft == '[' || chLeft == '{') {
                //为左括号 - 压栈
                stack.push(chLeft);
            }else {
                //为右括号 - 判断栈是不是空
                if (stack.isEmpty()) {
                    return false;
                }
                //判断右括号是否匹配
                char chright = stack.peek();//看一眼栈顶元素
                if (chright == '[' && chLeft == ']' || chright == '(' && chLeft == ')'
                        || chright == '{' && chLeft == '}') {
                    //匹配成功 - 弹出队头元素
                    stack.pop();
                }else {
                    //不匹配
                    return false;//不是有效的括号
                }
            }
        }
        //若字符串遍历完成但是栈不为空说明左括号较多
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    /*
     * Day 16
     * 1.队列实现栈
     * 2.栈实现队列
     * */
    // 1.队列实现栈
    class MyStack {
        Queue<Integer> queue;

        /** Initialize your data structure here. */
        public MyStack() {
            queue = new LinkedList<Integer>();
        }

        /** Push element x onto stack. */
        public void push(int x) {
            int n = queue.size();
            queue.offer(x);
            for (int i = 0; i < n; i++) {
                queue.offer(queue.poll());
            }
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return queue.poll();
        }

        /** Get the top element. */
        public int top() {
            return queue.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue.isEmpty();
        }
    }

    // 2.栈实现队列
    class MyQueue {
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;

        public MyQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        public void push(int x) {
            stack1.push(x);
        }

        public int pop() {
            if (empty()) {
                return -1;
            }
            if (stack2.empty()) {
                while (!stack1.empty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

        public int peek() {
            if (empty()) {
                return -1;
            }
            if (stack2.empty()) {
                while (!stack1.empty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }

        //判断是不是为空 - 如果两个栈都是空的，队列就是空的
        public boolean empty() {
            return stack1.empty() && stack2.empty();
        }
    }

    // 双向链表实现
    class MyLinkedList {
        class ListNode {
            public int val;//数值域
            public ListNode prev;//前面的地址
            public ListNode next;//后面的地址

            public ListNode(int val) {
                this.val = val;
            }
        }

        public ListNode head;//双向链表的头结点
        public ListNode tail;//双向链表的尾结点

        /*
         * NO.1
         * @ 打印双向链表每个节点的值
         * */
        public void disPlay() {
            ListNode cur = this.head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }

        /*
         * NO.2
         * @ 求双向链表元素个数
         * */
        public int size() {
            ListNode cur = this.head;
            int count = 0;//计数器
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }

        /*
         * No.3
         * @ 在双向链表中查找是否有key
         * */
        public boolean contains(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

        /*
         * NO.4
         * @ 头插法
         * */
        public void addFirst(int data) {
            ListNode node = new ListNode(data);//新节点
            //双向链表为空的情况
            if (this.head == null) {
                //头和尾直接赋给node结点
                this.head = node;
                this.tail = node;
            } else { //有很多结点的情况
                node.next = this.head;//node的next域指向head
                this.head.prev = node;//原head的prev域指向node的地址
                head = node;//将node结点改成新头结点
            }
        }

        /*
         * NO.5
         * @ 尾插法
         * */
        public void addLast(int data) {
            ListNode node = new ListNode(data);//新节点
            //双向链表为空的情况
            if (this.head == null) {
                this.head = node;
                this.tail = node;
            } else { //多个结点的情况
                this.tail.next = node;//尾结点地址域指向node结点
                node.prev = this.tail;//node指向它的前驱
                this.tail = node;//尾结点改成node
            }
        }

        /*
         * NO.6
         * @ 在任意位置插入第一个数据结点为0的下标
         * */
        //下表为逻辑上定义的下标
        public void addIndex(int index, int data) throws IndexWrong {
            //index位置要合法
            if (index < 0 || index > size()) {
                System.out.println("index位置不合法！！！");
                throw new RuntimeException("index位置不合法！！！");
            }

            //头插
            if (index == 0) {
                addFirst(data);
                return;
            }

            //尾插
            if (index == size()) {
                addLast(data);
                return;
            }
            ListNode cur = findIndexListNode(index);//此时cur即是index的位置

            //在中间插，不是头不是尾就是中间
            ListNode node = new ListNode(data);
            node.next = cur;//node的地址指向cur
            cur.prev.next = node;//index位置的前驱的地址指向node
            node.prev = cur.prev;//node前驱的地址指向cur的前驱
            cur.prev = node;//cur前驱的地址指向node
        }

        //求cur的位置
        private ListNode findIndexListNode(int index) {
            ListNode cur = this.head;
            while (index != 0) {
                cur = cur.next;//指向下一个
                index--;
            }
            return cur;
        }

        /*
         * NO.7
         * @ 删除第一次出现的key结点
         * */
        public void remove(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.val == key) {
                    //如果key在头结点
                    if (cur == this.head) {
                        this.head = this.head.next;//头结点指向它的下一个
                        if (this.head != null) {
                            this.head.prev = null;//改掉head指向前驱的地址
                        } else {
                            this.tail = null;//将tail指向空
                        }

                    } else { //如果key不是头结点
                        cur.prev.next = cur.next;//cur的前驱指向cur的后面
                        //cur不等于空说明cur此时不指向尾结点
                        if (cur.next != null) {
                            cur.next.prev = cur.prev;//cur后面的结点的前驱指向cur的前驱
                        } else { //指向尾结点
                            this.tail = cur.prev;//将tail前移一个结点的位置
                        }
                    }
                    return;
                }
                cur = cur.next;//指向下一个
            }
        }

        /*
         * NO.8
         * @
         * @ 删除所有值为key的结点
         * */
        public void removeAllKey(int key) {
            ListNode cur = this.head;
            while (cur != null) {
                if (cur.val == key) {
                    //如果key在头结点
                    if (cur == this.head) {
                        this.head = this.head.next;//头结点指向它的下一个
                        if (this.head != null) {
                            this.head.prev = null;//改掉head指向前驱的地址
                        } else {
                            this.tail = null;//将tail指向空
                        }

                    } else { //如果key不是头结点
                        cur.prev.next = cur.next;//cur的前驱指向cur的后面
                        //cur不等于空说明cur此时不指向尾结点
                        if (cur.next != null) {
                            cur.next.prev = cur.prev;//cur后面的结点的前驱指向cur的前驱
                        } else { //指向尾结点
                            this.tail = cur.prev;//将tail前移一个结点的位置
                        }
                    }
                }
                cur = cur.next;//指向下一个
            }
        }

        /*
         * NO.9
         * @ 清空双向链表
         * */
        public void clear() {
            ListNode cur = this.head;
            //清空中间的结点
            while (cur != null) {
                ListNode curNext = cur.next; //始终指向cur的下一个
                //置为空
                cur.prev = null;
                cur.next = null;
                cur = cur.next;//指向下一个
            }

            //两端的结点
            this.head = null;
            this.tail = null;
        }
    }

    // 顺序表练习
    class MyArrayList {
        private int[] nums;//未初始化的数组
        private int usedSize;// 记录有效的元素个数
        private static final int DEFAULT_SIZE = 10;

        public MyArrayList() {
            this.nums = new int[usedSize]; //数组个数为是个元素
        }

        // 打印表中的所有元素
        public void disPlay() {
            for (int i = 0; i < this.usedSize; i++) {
                System.out.print(this.nums[i] + " ");
            }
            System.out.println(); //换行
        }

        // 检查顺序表是否满了
        public boolean isFull() {
            // 获取表的长度
            int len = getSize();
            if (len >= this.usedSize) {
                return true; // 满了
            } else {
                return false; // 没满
            }
        }

        // 获取表的长度
        public int getSize() {
            return this.usedSize;
        }

        // 默认在表的末尾新增一个元素
        public void add(int data) {
            // 如果表满了就需要扩容
            if (isFull()) {
                // 扩容
                this.nums = Arrays.copyOf(this.nums, 2 * this.nums.length);
            }

            // UsedSize 就是数组末尾的下标
            this.nums[this.usedSize] = data;
            this.usedSize++; // 有效元素个数加一个
        }

        // 在表中指定位置插入一个元素
        public void add(int pos, int data) {
            // 负数下标或者大于表的有效元素个数不可以
            if (pos < 0 || pos >= this.usedSize) {
                throw new EmptyException("下标位置不合法！！！");
            }
            // 如果表满了就需要扩容
            if (isFull()) {
                System.out.println("顺序表满了！！！");
                this.nums = Arrays.copyOf(this.nums, 2 * this.nums.length);
            }
            // 开始找要插入的位置
            for (int i = this.usedSize - 1 ; i >= pos ; i--) {
                this.nums[i + 1] = this.nums[i];
            }
            // 插入元素
            this.nums[pos] = data;
            // 有效元素个数加一个
            this.usedSize++;
        }

        // 判断表是不是空的
        public boolean isEmpty() {
            return getSize() == 0;
        }

        // 判断是否包含某个元素
        public boolean contains(int toData) {
            if (isEmpty()) {
                // 表为空
            }
            return true;
        }

        // 查找某个对应元素的位置
        public int getelem(int toData) {
            for (int i = 0; i < this.getSize(); i++) {
                if (this.nums[i] == toData) {
                    // 找到了
                    return i;
                }
            }
            // 不存在返回 -1
            return -1;
        }

        // 获取某个元素的位置
        public int getElemPlace(int data) {
            // 表为空则不能获取
            if (isEmpty()) {
                // 抛异常提醒
                throw new EmptyException("当前顺序表为空！！！");
            }
            // 要查找的位置不能是负数，也不能超过元素个数
            if (data < 0 || data >= this.usedSize) {
                throw new EmptyException("获取下标位置不合法！！！");
            }
            return this.nums[data]; //直接返回下标即可
        }

        // 删除第一次出现的 Key 结点
        public void removeOne(int data) {
            // 表示空的就不能删除
            if (isEmpty()) {
                System.out.println("顺序表是空的！！！");
            }
            int index = getelem(data);
            if (index == -1) {
                // 不存在要删除的结点
                System.out.println("要删除的结点不存在！！！");
                return;
            }
            // 找到 data 的下标后才可以删除
            for (int i = index; i < this.usedSize - 1; i++) {
                // 从要删除的位置开始遍历
                // 后一个覆盖前一个删除
                this.nums[i] = this.nums[i + 1];
            }
            // 元素个数减一个
            this.usedSize--;
        }

        // 清空表
        public void clear() {
            this.usedSize = 0;
        }

        //给 pos 位置的元素更新为 value
        public void set(int pos, int value) {
            // 表不能是空的
            if (isEmpty()) {
                throw new EmptyException("表不能是空的！！！");
            }
            // pos 位置不能是负数或者超过元素个数
            if (pos < 0 || pos >= this.usedSize) {
                throw new EmptyException("下标位置不合法！！！");
            }
            // 开始更新
            this.nums[pos] = value;
        }
    }


    public static void main(String[] args) {
       DataStructureExercise dataStructureExercise = new DataStructureExercise();

       dataStructureExercise.createList(); //测试创建链表
       dataStructureExercise.disPlay();//测试打印链表


    }
}

